package LC;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/largest-number/description/
 * Given a list of non negative integers, arrange them such that they form the largest number.
 * For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
 * Note: The result may be very large, so you need to return a string instead of an integer.
 * Credits:
 * Special thanks to @ts for adding this problem and creating all test cases.
 */
public class LC_179_LargestNumber_Sort {
    public static void main(String[] args) {
        System.out.println(Solution.largestNumber(new int[]{3, 30, 34, 5, 9}));
        System.out.println(Solution_2.largestNumber(new int[]{3, 30, 34, 5, 9}));
    }

    static class Solution {
        static String largestNumber(int[] arr) {
            Integer[] array = new Integer[arr.length];
            int i = 0;
            for (int value : arr)
                array[i++] = Integer.valueOf(value);
//            Arrays.sort(array, new Comparator<Integer>() {
//                        @Override
//                        public int compare(Integer a1, Integer a2) {
//                            int l1 = a1 == 0 ? 1 : (int) Math.log10(Math.abs(a1)) + 1;
//                            int l2 = a2 == 0 ? 1 : (int) Math.log10(Math.abs(a2)) + 1;
//                            long aa1 = (long) (a1 * Math.pow(10, l2) + a2);
//                            long aa2 = (long) (a2 * Math.pow(10, l1) + a1);
//                            return aa1 > aa2 ? -1 : (aa1 == aa2 ? 0 : 1);
//                        }
//                    }
//            );
            Arrays.sort(array, (a1, a2) -> {
                        int l1 = a1 == 0 ? 1 : (int) Math.log10(Math.abs(a1)) + 1;
                        int l2 = a2 == 0 ? 1 : (int) Math.log10(Math.abs(a2)) + 1;
                        long aa1 = (long) (a1 * Math.pow(10, l2) + a2);
                        long aa2 = (long) (a2 * Math.pow(10, l1) + a1);
                        return Long.compare(aa2, aa1);
                    }
            );
            StringBuilder sb = new StringBuilder();
            for (Integer e : array)
                sb.append(e);
            return sb.toString().replaceFirst("^0+(?!$)", "");
        }
    }

    static class Solution_2 {
        static String largestNumber(int[] nums) {
            if (nums == null || nums.length == 0)
                return null;
            String[] str = new String[nums.length];
            for (int i = 0; i < nums.length; i++) {
                str[i] = String.valueOf(nums[i]);
            }
//            Arrays.sort(str, new Comparator<String>() {
//                public int compare(String a, String b) {
//                    String leftRight = a + b;
//                    String rightLeft = b + a;
//                    return -leftRight.compareTo(rightLeft);
//                }
//            });
            Arrays.sort(str, (a, b) -> {
                String leftRight = a + b;
                String rightLeft = b + a;
                return -leftRight.compareTo(rightLeft);
            });
            StringBuilder sb = new StringBuilder();
            for (String s : str) {
                sb.append(s);
            }
            while (sb.charAt(0) == '0' && sb.length() > 1)
                sb.deleteCharAt(0);
            return sb.toString();
        }
    }
}